/* ------------------------------------------------------------------------
 *
 * geqo_pool.cpp
 *	  Genetic Algorithm (GA) pool stuff
 *
 * Portions Copyright (c) 2020 Huawei Technologies Co.,Ltd.
 * Portions Copyright (c) 1996-2012, PostgreSQL Global Development Group
 * Portions Copyright (c) 1994, Regents of the University of California
 *
 * IDENTIFICATION
 * src/gausskernel/optimizer/geqo/geqo_pool.cpp
 *
 * -------------------------------------------------------------------------
 */
/* contributed by:
   =*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=
   *  Martin Utesch				 * Institute of Automatic Control	   *
   =							 = University of Mining and Technology =
   *  utesch@aut.tu-freiberg.de  * Freiberg, Germany				   *
   =*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=
 */
/* -- parts of this are adapted from D. Whitley's Genitor algorithm -- */
#include "postgres.h"
#include "knl/knl_variable.h"

#include <float.h>
#include <limits.h>
#include <math.h>

#include "optimizer/geqo_copy.h"
#include "optimizer/geqo_pool.h"
#include "optimizer/geqo_recombination.h"

static int compare(const void* arg1, const void* arg2);

/*
 * alloc_pool
 *		allocates memory for GA pool
 */
Pool* alloc_pool(PlannerInfo* root, int pool_size, int string_length)
{
    Pool* new_pool = NULL;
    Chromosome* chromo = NULL;
    int i;

    /* pool */
    new_pool = (Pool*)palloc(sizeof(Pool));
    new_pool->size = (int)pool_size;
    new_pool->string_length = (int)string_length;

    /* all chromosome */
    new_pool->data = (Chromosome*)palloc(pool_size * sizeof(Chromosome));

    /* all gene */
    chromo = (Chromosome*)new_pool->data; /* vector of all chromos */
    for (i = 0; i < pool_size; i++)
        chromo[i].string = (Gene*)palloc((string_length + 1) * sizeof(Gene));

    return new_pool;
}

/*
 * free_pool
 *		deallocates memory for GA pool
 */
void free_pool(PlannerInfo* root, Pool* pool)
{
    Chromosome* chromo = NULL;
    int i;

    /* all gene */
    chromo = (Chromosome*)pool->data; /* vector of all chromos */
    for (i = 0; i < pool->size; i++)
        pfree_ext(chromo[i].string);

    /* all chromosome */
    pfree_ext(pool->data);

    /* pool */
    pfree_ext(pool);
}

void random_init_pool(PlannerInfo* root, Pool* pool)
{
    Chromosome* chromo = (Chromosome*)pool->data;
    int i;

    for (i = 0; i < pool->size; i++) {
        init_tour(root, chromo[i].string, pool->string_length);
        pool->data[i].worth = geqo_eval(root, chromo[i].string, pool->string_length);
    }
}

/*
 * sort_pool
 *	 sorts input pool according to worth, from smallest to largest
 *
 *	 maybe you have to change compare() for different ordering ...
 */
void sort_pool(PlannerInfo* root, Pool* pool)
{
    qsort(pool->data, pool->size, sizeof(Chromosome), compare);
}

/*
 * compare
 *	 qsort comparison function for sort_pool
 */
static int compare(const void* arg1, const void* arg2)
{
    const Chromosome* chromo1 = (const Chromosome*)arg1;
    const Chromosome* chromo2 = (const Chromosome*)arg2;

    if (chromo1->worth - chromo2->worth == 0)
        return 0;
    else if (chromo1->worth > chromo2->worth)
        return 1;
    else
        return -1;
}

/* alloc_chromo
 *	  allocates a chromosome and string space
 */
Chromosome* alloc_chromo(PlannerInfo* root, int string_length)
{
    Chromosome* chromo = NULL;

    chromo = (Chromosome*)palloc(sizeof(Chromosome));
    chromo->string = (Gene*)palloc((string_length + 1) * sizeof(Gene));

    return chromo;
}

/* free_chromo
 *	  deallocates a chromosome and string space
 */
void free_chromo(PlannerInfo* root, Chromosome* chromo)
{
    pfree_ext(chromo->string);
    pfree_ext(chromo);
}

/* spread_chromo
 *	 inserts a new chromosome into the pool, displacing worst gene in pool
 *	 assumes best->worst = smallest->largest
 */
void spread_chromo(PlannerInfo* root, Chromosome* chromo, Pool* pool)
{
    int top, mid, bot;
    int i, index;
    Chromosome swap_chromo, tmp_chromo;

    /* new chromo is so bad we can't use it */
    if (chromo->worth > pool->data[pool->size - 1].worth)
        return;

    /* do a binary search to find the index of the new chromo */
    top = 0;
    mid = pool->size / 2;
    bot = pool->size - 1;
    index = -1;

    while (index == -1) {
        /* these 4 cases find a new location */
        if (chromo->worth <= pool->data[top].worth) {
            index = top;
        } else if (chromo->worth - pool->data[mid].worth == 0) {
            index = mid;
        } else if (chromo->worth - pool->data[bot].worth == 0) {
            index = bot;
        } else if (bot - top <= 1) {
            index = bot;
        } else if (chromo->worth < pool->data[mid].worth) {
        /*
         * these 2 cases move the search indices since a new location has not
         * yet been found.
         */
            bot = mid;
            mid = top + ((bot - top) / 2);
        } else { /* (chromo->worth > pool->data[mid].worth) */
            top = mid;
            mid = top + ((bot - top) / 2);
        }
    } /* ... while */

    /* now we have index for chromo */
    /*
     * move every gene from index on down one position to make room for chromo
     */
    /*
     * copy new gene into pool storage; always replace worst gene in pool
     */
    geqo_copy(root, &pool->data[pool->size - 1], chromo, pool->string_length);

    swap_chromo.string = pool->data[pool->size - 1].string;
    swap_chromo.worth = pool->data[pool->size - 1].worth;

    for (i = index; i < pool->size; i++) {
        tmp_chromo.string = pool->data[i].string;
        tmp_chromo.worth = pool->data[i].worth;

        pool->data[i].string = swap_chromo.string;
        pool->data[i].worth = swap_chromo.worth;

        swap_chromo.string = tmp_chromo.string;
        swap_chromo.worth = tmp_chromo.worth;
    }
}
